package Solutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/***
 * String permutations 求一个字符串中字符构成的全排列所有子串集合
 */
public class StringPermutations {
    /***
     * 返回给定字符串中所有字符的全排列字符串数组
     * @param string 给定的字符串
     * @return 结果集数组，去重复
     */
    public String[] stringPermutations(String string) {
        if (string == null || "".equals(string))
            throw new RuntimeException("The input string is null or the length is equals 0");
        if (string.length() == 1) return new String[]{string};// 当字符串的长度为1的时候，直接返回该字符串就可以了
        if (string.length() == 2) {
            // 字符串长度为 2 的时候，将其中一个反转即可，构成数组返回即可
            return  new String[]{new ReverseString().reverse(string), string};
        }
        List<String> resList = new ArrayList<>();// 用于存储结果的可变 List 集合
        for (int i = 0; i < string.length(); i++) {
            // 移除第 i 个字符后构成新的字符串递归调用该方法
            String[] res = stringPermutations(removeCharAt(string, i));
            for (String re : res) {
                // 将得到的结果数组，与之前去掉的字符拼接成新的字符串放入结果list中
                if(!resList.contains(string.charAt(i) + re))// 去重复
                    resList.add(string.charAt(i) + re);
            }
        }
        // 构造结果数组，将结果集list中的元素放置到结果数组中
        String[] result = new String[resList.size()];
        for (int i = 0 ; i < resList.size();i++) {
            result[i] = resList.get(i);
        }
        return result;// 返回结果数组
    }

    /***
     * 将给定字符串的第i个字符去掉，构成新的String对象返回出去
     * @param string 等待处理的字符串
     * @param index 需要删除的字符的位置
     * @return sb.toString()为构造的新的String对象
     */
    private String removeCharAt(String string, int index) {
        char[] chars = string.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if (i != index) {// 排除需要删除的字符
                sb.append(chars[i]);
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new StringPermutations().stringPermutations("123456")));
    }
}
